#!/usr/bin/python3


def make_mat(m, n):
    mat = []
    for i in range(m):
        mat.append([None] * n)
    return mat


def print_lcs(x, b, i, j):
    if i == 0 or j == 0:
        return
    if b[i][j] == 1:
        print_lcs(x, b, i-1, j-1)
        print(x[i-1], end="")
    elif b[i][j] == 2:
        print_lcs(x, b, i - 1, j)
    elif b[i][j] == 3:
        print_lcs(x, b, i, j - 1)


def lcs(x, y):
    m = len(x)
    n = len(y)
    c = make_mat(m+1, n+1)
    b = make_mat(m+1, n+1)  # 1: left-up, 2: left, 3: up
    for i in range(0, m+1):
        c[i][0] = 0
    for i in range(1, n+1):
        c[0][i] = 0

    for i in range(1, m+1):
        for j in range(1, n+1):
            if x[i-1] == y[j-1]:
                c[i][j] = c[i-1][j-1] + 1
                b[i][j] = 1
            elif c[i-1][j] >= c[i][j-1]:
                c[i][j] = c[i-1][j]
                b[i][j] = 2
            else:
                c[i][j] = c[i][j - 1]
                b[i][j] = 3

        print_lcs(x, b, m, n)

if __name__ == '__main__':
    x = "acgatct"
    y = "gctact"
    lcs(x, y)

    x = "MAEEEVAKLEKHLMLLRQEYVKLQKKLAETEKRCALLAAQANKESSSESFISRLLAIVAD"
    y = "MAEEEVAKLEKHLMLLRQEYVKLQKKLAETEKRCTLLAAQANKENSNESFISRLLAIVAG"
    lcs(x, y)
